# -*- coding:utf-8

# 5347. 使网格图至少有一条有效路径的最小代价 显示英文描述
# 用户通过次数0
# 用户尝试次数0
# 通过次数0
# 提交次数0
# 题目难度Hard
# 给你一个 m x n 的网格图 grid 。 grid 中每个格子都有一个数字，对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况：
#
# 1 ，下一步往右走，也就是你会从 grid[i][j] 走到 grid[i][j + 1]
# 2 ，下一步往左走，也就是你会从 grid[i][j] 走到 grid[i][j - 1]
# 3 ，下一步往下走，也就是你会从 grid[i][j] 走到 grid[i + 1][j]
# 4 ，下一步往上走，也就是你会从 grid[i][j] 走到 grid[i - 1][j]
# 注意网格图中可能会有 无效数字 ，因为它们可能指向 grid 以外的区域。
#
# 一开始，你会从最左上角的格子 (0,0) 出发。我们定义一条 有效路径 为从格子 (0,0) 出发，每一步都顺着数字对应方向走，最终在最右下角的格子 (m - 1, n - 1) 结束的路径。有效路径 不需要是最短路径 。
#
# 你可以花费 cost = 1 的代价修改一个格子中的数字，但每个格子中的数字 只能修改一次 。
#
# 请你返回让网格图至少有一条有效路径的最小代价。

from typing import  List
class Solution:

    def __init__(self):
        self._vivited = []
        self._m = 0
        self._n = 0

    def isValid(self,i,j):
        return i>=0 and i<self._m and j>=0 and j< self._n


    def minCost(self, grid: List[List[int]]) -> int:
        if grid.__len__() == 1 and grid[0].__len__() == 1:
            return 0
        self._m = grid.__len__()
        self._n = grid[0].__len__()
        self._vivited = [[0 for j in range(grid[0].__len__())] for i in range(grid.__len__())]

        # self._vivited[0][0] = 1

        cost = 0
        # cur = [0,0]
        row ,col = 0,0
        curVarLis = []
        while self.isValid(row,col) and self._vivited[row][col] == 0: ##合法且未被访问过
            self._vivited[row][col] = 1
            curVarLis.append((row,col))
            direct = grid[row][col]
            if direct == 1:
                col += 1
            elif direct == 2:
                col -= 1
            elif direct == 3:
                row += 1
            elif direct == 4:
                row -= 1

        while self._vivited[-1][-1] == 0:
            cost += 1
            preVarLis = curVarLis.copy()
            curVarLis = []
            while preVarLis.__len__()>0:
                r,c  = preVarLis.pop(0)

                def extend(newR,newC):
                    while self.isValid(newR, newC) and self._vivited[newR][newC] == 0:  ##合法且未被访问过
                        self._vivited[newR][newC] = 1
                        curVarLis.append((newR, newC))
                        direct = grid[newR][newC]
                        if direct == 1:
                            newC += 1
                        elif direct == 2:
                            newC -= 1
                        elif direct == 3:
                            newR += 1
                        elif direct == 4:
                            newR -= 1

                extend(r+1,c)
                extend(r-1,c)
                extend(r,c+1)
                extend(r,c-1)
        return cost

cost = Solution().minCost([[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]])
print(cost)








